import java.util.Stack;

class Node{
    int val;
    Node left;
    Node right;
    Node(int val){
        this.val=val;
        this.left=null;
        this.right=null;
    }
}
public class preorderTraversal {
    // 递归的用法：
    public static void pre(Node root){
        if(root!=null){
            System.out.print(root.val+" ");
            pre(root.left);
            pre(root.right);
        }
    }

    //非递归实现：
    public static void pre2(Node root){
        Stack<Node> stack=new Stack<>();
        if(root!=null){
            stack.push(root);
        }
        while (!stack.isEmpty()){
            Node curr= stack.pop(); //注意栈的顺序
            System.out.print(curr.val+" ");
            if(curr.right!=null){
                stack.push(curr.right);
            }
            if(curr.left!=null){
                stack.push(curr.left);
            }
        }
    }

    public static void main(String[] args){
        Node root=new Node(1);
        root.left=new Node(2);
        root.right=new Node(3);
        root.left.left=new Node(4);
        root.left.right=new Node(5);
        root.right.left=new Node(6);
        root.right.right=new Node(7);
        System.out.println("pre(root)= ");
        pre(root);
        System.out.println();
        System.out.println("pre2(root)= ");
        pre2(root);
    }
}
